public class InsertionSort<T extends Comparable<T>> {
    /*
2 3 4 0 1 9 5
j     i
索引解释：
[0, i)是有序的
     */
    public T[] insertionSort(T[] data) {

        for (int i = 1; i < data.length; i++) {

            for (int j = 0; j < i; j++) {
                if (data[i].compareTo(data[j]) < 0) {
                    //i位置元素插入到j位置
                    //[j, i)的元素整体向后搬移
                    T tem = data[i];
                    for (int k = i; k > j; k--) {
                        data[k] = data[k-1];
                    }
                    data[j] = tem;
                }
            }
        }
        return data;
    }

    public static void main(String[] args) {
        Integer[] arr = {2, 3, 4, 0, 1, 9, 5};
        InsertionSort<Integer> insertionSort = new InsertionSort<>();
        insertionSort.insertionSort(arr);
        System.out.println();
    }
}
